\documentclass[a4paper,10pt]{article}

\usepackage{graphicx}
\usepackage[cm]{fullpage}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}

% commands for setting up the page
\parindent0mm
\pagestyle{empty}

\sloppy

% environment for "exercise"
\newcounter{exc}
\newenvironment{exercise}[1]%
{\refstepcounter{exc}\textbf{Exercise \arabic{exc}} \emph{#1}\\}
{

\hrulefill\medskip}%
\renewcommand{\labelenumi}{(\alph{enumi})}

\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\vc}[1]{\boldsymbol{#1}}

\begin{document}

%% Header
\begin{center}
  {\large \bf Exercises for\\
    Mathematical Programming\\
    186.835 VU 3.0 - SS 14}\\
  \bigskip
  Last update: \today
\end{center}

\hrulefill\medskip

Group members:
\begin{enumerate}
\item Christian Hafner, 0925172, chafner@cg.tuwien.ac.at
\item Klemens Jahrmann, 0826080, klemens.jahrmann@tuwien.ac.at
\item Kevin Streicher, 1025890, e1025890@student.tuwien.ac.at
\end{enumerate}


\hrulefill\medskip


\begin{exercise}{Network Design}\label{ex:nd1}
We are given a directed graph $G=(V,A)$ and a demand or supply $b_i$ for each $i\in V$, such that $\sum_{i\in V} b_i=0$. 
There are two types of costs: transportation costs $c_{ij}$ of shipping one unit from node $i$ to node $j$, and building costs of establishing a link $(i,j)$ between nodes $i$ and $j$. If a link must be established on arc $(i,j)$ there are two possibilities:
(i) establish a link with costs $d_{ij}^1$ and capacity $u_{ij}^1$, or (ii) a link with costs $d_{ij}^2$ and capacity $u_{ij}^2$. Assume that $d_{ij}^1<d_{ij}^2$ and $u_{ij}^1<u_{ij}^2$ and that at most one link can be established on each arc. A network has to be built that satisfies all demands and minimizes the total building and transportation costs. Formulate the problem as a (mixed) integer linear program.

\medskip
\textbf{Objective Function}
\medskip

$$\min \sum_{a=(i,j)\in A} f_{ij}c_{ij}+x_{ij}^1d_{ij}^1+x_{ij}^2d_{ij}^2$$

\medskip
\textbf{Variables}
\medskip
\begin{itemize}
\item Decision variables $x_{ij}^t \forall a=(i,j)\in A,x_{ij}^t \in \left\{0,1\right\},t\in \left\{1,2\right\}$

$x_{ij}^t$ is 1 iff a link of type $t$ is established on arc $a=(i,j)$

\item Flow variables $f_{ij},f_{ij}\geq0$

$f_{ij}$ defines the amount of positive supply flowing over arc $a=(i,j)$ from node $i$ to $j$
\end{itemize}
\medskip
\textbf{Constraints}
\begin{equation}\label{eq:oneLinkPerArc}
\forall (i,j)\in A:x_{ij}^1+x_{ij}^2 \leq 1
\end{equation}
We either may built a link of type 1 or of type 2.
\begin{equation}\label{eq:maxCapacity}
\forall (i,j)\in A:f_{ij}\leq x_{ij}^1*u_{ij}^1+x_{ij}^2*u_{ij}^2
\end{equation}
Equation~\ref{eq:oneLinkPerArc} assures that only one type of links per arc can be chosen therefore this constraint assures that the flow can not exeed the capacity of the chosen type. 
\begin{equation}\label{eq:supplyDemand}
\forall j \in V \sum_{\forall i:(i,j) \in A}f_{ij}-\sum_{\forall i:(j,i) \in A}f_{ji}=-b_i
\end{equation}
When $+b_i$ is interpreted as supply and $-b_i$ as demand and we do know that the sum of all supplies and demands is 0, we also know that every supply is needed to fulfil the demand. This constraints says, that for each node the difference of inflow-outflow needs to be exactly $-b_i$.

\begin{enumerate}
\item Supply node without ingoing arcs, it must send out exactly $b_i$ supply
\item Demand node without outgoing arcs, it must get exactly $b_i$ supply
\item (Possible) Intermediate nodes, all flow dedicated to other nodes needs to leave the node which results in a difference of 0. The excess flow can be treated as a case of supply or demand.
\end{enumerate}



\end{exercise}

\begin{exercise}{Job Shop Scheduling}\label{ex:jss}
A factory consists of $m$ machines $M_1, \dots, M_m$, and needs to process $n$ jobs every day. Job $j$ needs to be processed once by each machine in the order $(M_{j(1)},\dots,M_{j(m)})$. Machine $M_i$ takes time $p_{ij}$ to process job $j$. A machine can only process one job at a time, and once a job is started on any machine, it must be processed to completion. The objective is to minimize the sum of the completion times of all the jobs. Formulate the problem as a (mixed) integer linear program.

\medskip
\textbf{Variables}
\medskip

The starting time of of job $j$ on machine $i$ is represented by $s_{i,j} \in \mathbb{R}$.

The variables $o^i_{j,k} \in \{0,1\}$ indicate the ordering of jobs $j,k$ on machine $i$. $o^i_{j,k}$ is 0 if $j$ is processed before $k$ on machine $i$ and 1 otherwise. The variable $o^i_{j,k}$ is only defined for $j<k$.

\medskip
\textbf{Model}
\medskip

The problem of minimizing the sum of the completion times of all the jobs is equivalent to minimizing the sum of each job's starting time on its last machine. Therefore the objective function is

\begin{equation}
	\min \sum_{j \in \{1,\ldots,n\}} s_{j(m),j}.
\end{equation}

The sum of the completion times can be found by adding the sum of each job's processing time on its last machine to the optimal cost.

The linear program uses the following constraints:
\begin{align}
	\forall i \in \{1,\ldots,m-1\}, j \in \{1,\ldots,n\}&: s_{j(i),j} + p_{j(i),j} \leq s_{j(i+1),j} \label{eq:job1}\\
	\forall i \in \{1,\ldots,m\}, \{j,k\} \subseteq \{1,\ldots,n\}, j<k&: s_{i,j} + p_{i,j} \leq s_{i,k} + M*o^i_{jk}\label{eq:job2} \\
	\forall i \in \{1,\ldots,m\}, \{j,k\} \subseteq \{1,\ldots,n\}, j<k&: s_{i,k} + p_{i,k} \leq s_{i,j} + M * (1-o^i_{jk}) \label{eq:job3}
\end{align}
$M$ is a large number, for example the sum of all processing times. One could also use a separate $M_i$ for each machine $i$ in Eqns.\ \ref{eq:job2} and \ref{eq:job3}, where $M_i$ is the sum of all processing times on machine $i$.

Eqn.\ \ref{eq:job1} ensures that a job's part finishes on one machine before its next part is started on another machine.

Eqns.\ \ref{eq:job2} and \ref{eq:job3} sort all job executions per machine, s.t.\ no two jobs are executed at the same time on the same machine. In case $o^i_{jk} = 0$, Eqn.\ \ref{eq:job3} is invalidated and Eqn.\ \ref{eq:job2} ensures that job $j$ is executed before job $k$ on machine $i$. The converse is true in case $o^i_{jk} = 1$.

\end{exercise}

\begin{exercise}{Sports League}\label{ex:sl}
The season in a sports league with $n$ teams has started. Now each team plays against each other team at home and away, so each team plays exactly $2(n-1)$ games. In case of a win a team receives three points, in case of a draw one point, and in case of a loss zero points. After the season the $k$ worst teams with respect to the total number of achieved points get relegated. The task is now to determine the minimum number of points a team has to achieve to have a guarantee that it is not relegated in any season outcome. Formulate the problem as a (mixed) integer linear program. \\
Optional tasks (one extra point per task): 
\begin{itemize}
 \item Is it possible to state an explicit function $f(n,k)$ to compute this minimum number of points?
 \item Solve the problem for $n=18$ and $k=3$ (e.g., by using CPLEX or the GNU Linear Programming Kit (http://www.gnu.org/software/glpk/).
\end{itemize}

\medskip
\textbf{Objective Function}
\medskip

$$\max \hspace{5pt} p_{k}$$

\medskip
\textbf{Variables}
\medskip
\begin{itemize}
\item Teams $T = \left\{1,\dots,n\right\}$ \\ Set of $n$ teams in the league.
\item Win variable $w_{ij} \in \left\{0,1,2\right\} \forall i,j \in T$ \\ Amount of wins of team $i$ against team $j$.
\item Draw variable $d_{i,j} \in \left\{0,1,2\right\} \forall i,j \in T, i < j$ \\ Amount of draws between team $i$ and team $j$, each pair is only counted once.
\item Point variable $p_i \in \mathbb{R} \; \forall i \in T$ \\ Amount of points of team $i$.
\end{itemize}

\medskip
\textbf{Constraints}
\medskip
\begin{equation}
\forall i,j \in T, i<j : w_{ij} + w_{ji} + d_{ij} = 2
\end{equation}
Two teams play exactly two times.

\begin{equation}
\forall i \in T: p_i= \sum_{i<j} d_{ij} + \sum_{j<i} d_{ji} + 3 \sum_{j=1}^n w_{ij}
\end{equation}
The points are accumulated for each team.
\begin{equation}
\forall i \in T \setminus \{n\} : p_i \leq p_{i+1}
\end{equation}
Points are sorted in ascending order.

The state of the variables for the optimal solution reflects a season where team $k$ is relegated with the maximum number of points possible. This implies that a team with $1+p_k$ points cannot have rank $k$ and be relegated, thus this is the solution to the problem.

The included file \texttt{tournament.cpp} contains the relevant part of our CPLEX model for this problem.

Is there a formula? Yes!\footnote{\url{http://www.gutefrage.net/frage/serie-a---minimale-punktzahl-zum-nicht-abstieg}} We found this formula online but created our own version that has a more intuitive explanation: $6(k-1) + 3(n-k) + 1.$

The case in which the $k$-th team has the most points but is still in danger of relegation is the following: All teams between ranks $k$ and $n$ have an equal number of points, where this number is the highest possible. This number of points is achieved if every team between ranks $k$ and $n$ wins every match against teams 1 to $(k-1)$. The matches among teams between $k$ and $n$ are perfectly balanced s.t.\ each team wins once and loses once against every other team. The matches among teams 1 to $(k-1)$ can be all draws or any other configuration where none of the teams achieves as many points as team $k$. The number of points achieved by team $k$ in this scenario is thus $p_{k} = 6(k-1) + 3(n-k).$ The solution to the problem is $1+p_k$.

Setting $n=18$ and $k=3$ yields the value 58 which was also found by our linear program.
\end{exercise}

\begin{exercise}{Minimum Spanning Tree Problem}\label{ex:mstp}
 Consider the minimum spanning tree problem  (MSTP). Given an undirected graph $G=(V,E)$, $n=|V|$, $m=|E|$, and edge weights $w_e\in \R_+$, $\forall e\in E$, we want to identify a minimum weight spanning tree. Assume that you did already model this problem as an integer linear program using single-commodity flows (SCF), given by \eqref{eq:scf-obj}--\eqref{eq:scf-end}, and multi-commodity flows (MCF). For the latter, you derived both an undirected formulation called (uMCF), given by \eqref{eq:umcf-obj}--\eqref{eq:umcf-end}, and a directed formulation called (dMCF) which is given by \eqref{eq:dmcf-obj}--\eqref{eq:dmcf-end}. All your formulations use node $1\in V$ as root node (i.e., source of your flows).
Your formulations utilize variables $x_e\in \{0,1\}$, $\forall e\in E$, indicating whether or not edge $e$ is part of the solution and variables $y_{ij}$, $\forall (i,j)\in A=\{(i,j),(j,i)\mid \{i,j\}\in E\}$, indicating whether or not arc $(i,j)$ is part of the solution.
Furthermore, flow variables $0\le f_{ij}\le n-1$ indicating the amount of flow on arc $(i,j)\in A$ are used in the SCF formulation and flow variables $0\le f_{ij}^k\le 1$ indicating the amount of flow from $1$ to $k\in V\setminus \{1\}$ on arc $(i,j)$ in the MCF formulations.

\begin{minipage}[t]{.44\textwidth}
\begin{footnotesize}
   \begin{align}
      \mbox{(SCF)}\ & \min \sum_{e\in E} w_e x_e \label{eq:scf-obj}\\
      \mathrm{s.t.}\ & \sum_{(1,j) \in A} f_{1j} - \sum_{(j,1) \in A} f_{j1} = n-1 \label{eq:scf-initflow} \mspace{-100mu}\\
      & \sum_{(i,j)\in A} f_{ij} - \sum_{(j,i)\in A} f_{ji} = -1,\ \forall i\in V\setminus \{1\} \label{eq:scf-consumeflow} \\
      & f_{ij} \leq (n-1) x_e,\ \forall e=\{i,j\}\in E \label{eq:scf-flowbound1} \\
      & f_{ji} \leq (n-1) x_e,\ \forall e=\{i,j\}\in E \label{eq:scf-flowbound2}\\
      & \sum_{e \in E} x_e = n-1 \\
      & f_{ij}\ge 0,\ \forall (i,j)\in A \\
      & x_e\in \{0, 1\},\ \forall e\in E \label{eq:scf-end}
   \end{align}
\end{footnotesize}
\end{minipage}\ \ 
\begin{minipage}[t]{.55\textwidth}
\begin{footnotesize}
   \begin{align}
        \mbox{(uMCF)}\ & \min \sum_{e\in E} w_e x_e \label{eq:umcf-obj}\\
        \mathrm{s.t.}\ & \sum_{(i,j)\in A} f_{ij}^k - \sum_{(j,i)\in A} f_{ji}^k = \begin{cases}
                                                                                                        1 & \mbox{ if $i=1$}\\
													-1 & \mbox{ if $i=k$}\\
													 0 & \mbox{ else}
													\end{cases},\ \forall k\in V\setminus \{1\}, \forall i\in V \\
        & f_{ij}^k \le x_e,\ \forall k\in V\setminus \{1\},\ \forall e=\{i,j\}\in E \\
	& f_{ji}^k \le x_e,\ \forall k\in V\setminus \{1\},\ \forall e=\{i,j\}\in E \\	
        & \sum_{e \in E} x_e = n-1 \\
	& f_{ij}^k \ge 0,\ \forall k\in V\setminus \{1\},\ \forall (i,j)\in A \\
        & x_e \in \{0,1\},\ \forall e\in E \label{eq:umcf-end}
      \end{align}
\end{footnotesize} 
\end{minipage}

\begin{footnotesize}
 \begin{align}
        \mbox{(dMCF)}\ & \min \sum_{e\in E} w_e x_e \label{eq:dmcf-obj}\\
        \mathrm{s.t.}\ & \sum_{(i,j)\in A} f_{ij}^k - \sum_{(j,i)\in A} f_{ji}^k = \begin{cases}
                                                                                                        1 & \mbox{ if $i=1$} \\
													-1 & \mbox{ if $i=k$} \\
													 0 & \mbox{ otherwise}
													\end{cases},\ \forall k\in V\setminus \{1\}, \forall i\in V \\
        & f_{ij}^k\le y_{ij},\ \forall k\in V\setminus \{1\},\ \forall (i,j)\in A \\
        & \sum_{(i,j)\in A} y_{ij} = n-1 \\
	& y_{ij} + y_{ji} = x_e,\ \forall e=\{i,j\}\in E \\
	& f_{ij}^k\ge 0,\ \forall k\in V\setminus \{1\},\ \forall (i,j)\in A \\
	& x_e\ge 0,\ \forall e\in E \\
	& y_{ij}\in \{0,1\},\ \forall (i,j)\in A \label{eq:dmcf-end}
 \end{align}
\end{footnotesize}

Assume that you already know that (dMCF) is at least as strong as (uMCF) which in turn is at least as strong as (SCF).
(Optional task: You can earn an extra point if you prove these relations.)
\smallskip

Show that 
\begin{itemize}
 \item (dMCF) is stronger than (uMCF)
 \item (uMCF) is stronger than (SCF)
\end{itemize}

\medskip
\textbf{(dMCF) is at least as strong as (uMCF)}
\medskip

To show this relationship, we provide a mapping that maps any feasible solution of LP(dMCF) to a solution of LP(uMCF) such that the values for the common variables of LP(dMCF) and LP(uMCF) remain unchanged. We then prove that the constraints of LP(uMCF) hold for the resulting solution.

Let $x_e, f^k_{ij}, y_{ij}$ for the index ranges described above denote a feasible solution to LP(dMCF). The mapping is the identity. The following calculations provide proofs for the constraints from LP(uMCF) that are not already given by LP(dMCF):
\begin{align}
\sum_{e \in E} x_e = \sum_{\{i,j\} \in E} (y_{ij} + y_{ji}) = \sum_{(i,j) \in A} y_{ij} = n-1. \\
f^k_{ij} \leq y_{ij} \leq y_{ij} + y_{ji} = x_e.
\end{align}

\medskip
\textbf{(uMCF) is at least as strong as (SCF)}
\medskip

Let $x_e, f^k_{ij}, y_{ij}$ denote a feasible solution to LP(uMCF). We map this onto a solution $x_e, f_{ij}$ for LP(SCF) by setting
\begin{equation}
\forall (i,j) \in A: f_{ij} := \sum_{k \in V \setminus \{1\}} f^k_{ij}. \\
\end{equation}

Proof for Eqns. \ref{eq:scf-flowbound1} and \ref{eq:scf-flowbound2}:
\begin{align}
f_{ij} = \sum_{k \in V \setminus \{1\}} f^k_{ij} \leq \sum_{k \in V \setminus \{1\}} x_e = (n-1)x_e.
\end{align}

Proof for Eqn. \ref{eq:scf-initflow}:
\begin{align}
\sum_{(1,j) \in A} f_{1j} - \sum_{(j,1) \in A} f_{j1} =
\sum_{(1,j) \in A} \sum_{k \in V \setminus \{1\}} f^k_{1j} - \sum_{(j,1) \in A} \sum_{k \in V \setminus \{1\}} f^k_{j1} =  \nonumber \\
\sum_{k \in V \setminus \{1\}} ( \sum_{(1,j) \in A} f^k_{1j} - \sum_{(j,1) \in A} f^k_{j1}) = \sum_{k \in V \setminus \{1\}} 1 = n-1.
\end{align}

Proof for Eqn. \ref{eq:scf-consumeflow}:
\begin{align}
\sum_{(i,j)\in A} f_{ij} - \sum_{(j,i)\in A} f_{ji} = \sum_{(i,j)\in A} \sum_{k \in V \setminus \{1\}} f^k_{ij} - \sum_{(j,i)\in A} \sum_{k \in V \setminus \{1\}} f^k_{ji} = \nonumber \\
\sum_{k \in V \setminus \{1\}} ( \sum_{(i,j)\in A} f^k_{ij} - \sum_{(j,i)\in A} f^k_{ji}) = (f^i_{ij} - f^i_{ji}) + \sum_{k \in V \setminus \{1\}} ( \sum_{\substack{(i,j)\in A \\ i \neq k}} f^k_{ij} - \sum_{\substack{(j,i)\in A \\ i \neq k}} f^k_{ji}) = \nonumber \\
-1 + \sum_{k \in V \setminus \{1\}} 0 = -1.
\end{align}


\medskip
\textbf{(dMCF) is stronger than (uMCF)}
\medskip

To show that (dMCF) is stronger than (uMCF), we provide a feasible solution of the LP-relaxation of (uMCF) and show that the projection of this solution onto the common variables of (uMCF) and (dMCF) cannot be extended to form a feasible solution of the LP-relaxation of (dMCF).

Consider the solution from Fig. \ref{fig:ex4graph2}. The value of the flow variables not present in the figure is 0. In order to satisfy the demand of nodes 2 and 3, 0.75 units can be transferred directly from node 1. The remaining 0.25 units for node 2 can only travel via nodes 3 and 4, the 0.25 units for node 3 only via nodes 2 and 4. Therefore there is a flow of at least 0.25 from 3 to 4 and from 4 to 3. But in order to find a feasible solution for LP(dMCF) that uses the same values for $x_e \forall e \in E$, we would need to find $y_{3,4}$ and $y_{4,3}$ with $y_{3,4}+y_{4,3}=0.25$, where a flow of at least 0.25 is permitted in both directions. This is impossible and therefore it holds that (dMCF) is stronger than (uMCF) under the assumption that the former is at least as strong as the latter.

\begin{figure}[ht!]
\centering
\includegraphics[height=80mm]{ex4graph2.png}
\caption{Solution to LP(uMCF).}
\label{fig:ex4graph2}
\end{figure}

\medskip
\textbf{(uMCF) is stronger than (SCF)}
\medskip

To show that (uMCF) is stronger than (SCF), consider the solution to LP(SCF) in Fig. \ref{fig:ex4graph1}. In order to satisfy the demand of node 2 with the constraints of LP(uMCF), only 0.2 units can be transferred directly from node 1. At most 0.3 units can arrive from node 3 and therefore no feasible solution with the same values for $x_e \forall e \in E$ exists.

\begin{figure}[ht!]
\centering
\includegraphics[height=50mm]{ex4graph1.png}
\caption{Solution to LP(SCF).}
\label{fig:ex4graph1}
\end{figure}

\end{exercise}

\end{document}
